﻿using System;
using System.Collections.Generic;
using System.Text;
using System.Linq;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0134_FindTarget : IAlgorithm
    {
        // 653. 两数之和 IV - 输入 BST

        // 给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

        // 提示:
        //   二叉树的节点个数的范围是[1, 10^4].
        //   -10^4 <= Node.val <= 10^4
        //   root 为二叉搜索树
        //   -10^5 <= k <= 10^5

        public void Test()
        {
            // 算法参数定义

            // 算法执行与打印
            //Console.WriteLine(Algorithm());
            //var res = Algorithm(param);
            //foreach (var item in res)
            //{
            //    foreach (var iitem in item)
            //    {
            //        Console.Write(iitem + " ");
            //    }
            //    Console.WriteLine();
            //}
        }

        // 算法
        public bool FindTarget(TreeNode root, int k)
        {
            var set = new HashSet<int>();
            var queue = new Queue<TreeNode>();
            queue.Enqueue(root);
            while (queue.Count > 0)
            {
                if (queue.Peek() != null)
                {
                    TreeNode node = queue.Dequeue();
                    if (set.Contains(k - node.val))
                        return true;
                    set.Add(node.val);
                    queue.Enqueue(node.right);
                    queue.Enqueue(node.left);
                }
                else
                    queue.Dequeue();
            }
            return false;
        }
    }
}
